package com.zj.leetcode.medium.greed;

/**
 * @program: algorithm
 * @description: 有效的括号字符串
 * 678 valid-parenthesis-string
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class ValidParenthesisString {
    public static void main(String[] args) {
        String s = "*()";
//        String s = "(*";
//        String s = "(((((*(()((((*((**(((()()*)()()()*((((**)())*)*)))))))(())(()))())((*()()(((()((()*(())*(()**)()(())";
        Solution solution = new ValidParenthesisString().new Solution();
        System.out.println(solution.checkValidString(s));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean checkValidString(String s) {
            int low = 0, high = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    low++;
                    high++;
                } else if (s.charAt(i) == ')') {
                    low--;
                    high--;
                } else {
                    low--;
                    high++;
                }
                if (high < 0) {
                    return false;
                }
                if (low < 0) {
                    low = 0;
                }
            }
            return low==0;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
